#include <iostream>
#include <fstream>
#include <vector>
#include <string>

// 回溯函数，用于生成格雷码
void backtrack(int n, std::vector<std::string>& codes, std::string current_code) {
    if (current_code.length() == n) {
        codes.push_back(current_code);
        return;
    }

    // 递归调用回溯函数生成格雷码
    backtrack(n, codes, current_code + '0'); // 在当前格雷码后追加 '0'
    backtrack(n, codes, current_code + '1'); // 在当前格雷码后追加 '1'
}

// 生成格雷码的函数
std::vector<std::string> generateGrayCode(int n) {
    std::vector<std::string> codes;
    std::string current_code;

    // 调用回溯函数生成格雷码
    backtrack(n, codes, current_code);

    return codes;
}

int main() {
    std::ifstream inputFile("input.txt"); // 打开输入文件
    std::ofstream outputFile("output.txt"); // 创建输出文件

    if (!inputFile) {
        std::cerr << "无法打开 input.txt 文件" << std::endl; // 输出错误信息
        return 1;
    }

    if (!outputFile) {
        std::cerr << "无法创建 output.txt 文件" << std::endl; // 输出错误信息
        return 1;
    }

    int n;
    inputFile >> n; // 从输入文件读取 n 的值

    std::vector<std::string> grayCodes = generateGrayCode(n); // 生成格雷码

    std::cout << "格雷码为：" ;
    for (const std::string& code : grayCodes) {
        outputFile << code << std::endl; // 将格雷码写入输出文件
        std::cout << code << std::endl; // 在控制台输出格雷码
    }

    inputFile.close(); // 关闭输入文件
    outputFile.close(); // 关闭输出文件

    std::cout << "已写入 output.txt 文件" << std::endl; // 输出成功信息

    return 0;
}